package euler.p101_150;

import euler.MainEuler;

public class Euler113 extends MainEuler {

    /*
        Working from left-to-right if no digit is exceeded
        by the digit to its left it is called an increasing
        number; for example, 134468.

        Similarly if no digit is exceeded by the digit to its
         right it is called a decreasing number; for example, 66420.

        We shall call a positive integer that is neither
        increasing nor decreasing a "bouncy" number; for example,
        155349.

        As n increases, the proportion of bouncy numbers
        below n increases such that there are only 12951 numbers
        below one-million that are not bouncy and
        only 277032 non-bouncy numbers below 10^10.

        How many numbers below a googol (10^100) are not bouncy?

     */

	public String resolve() throws Exception {
        int d = 2;
        int p = (int)Math.pow(10, d);


        int increasing = 0;
        int palin = 0;
        int decreasing = 0;
        for (int i = 1; i <= p; i++) {
            if (isIgual(i)) {
                palin++;
            }
            if (isDecreasing(i)) {
                decreasing++;
            }
            if (isIncreasing(i)) {
                increasing++;
            }
        }

        System.out.println("decreasing " + (decreasing));
        System.out.println("increasing " + (increasing));
        System.out.println("palin " + (palin));
        System.out.println("total " + (decreasing+increasing-palin));
        System.out.println("total2 " + (countIncreasing(9,0,d)+countDecreasing(9,0,d,true)-palin));

        return null;
    }

    private boolean isIgual(int n) {
        int d = n % 10;
        boolean decreasing = true;
        while (decreasing && n > 0) {
            int da = n % 10;
            n/=10;
            if (d != da) {
                return false;
            }
        }

        return true;
    }

    private int countIncreasing(int max, int min, int pos) {
        if (pos == 0) {
            return 1;
        }
        int count = 0;
        for (int i = min; i <= max; i++) {
            count+=countIncreasing(max,i,pos-1);
        }

        return count;
    }

    private int countDecreasing(int max, int min, int pos, boolean trailing0) {
        if (pos == 0) {
            return 1;
        }
        int count = 0;
        for (int i = max; i >= min; i--) {
            count+=countDecreasing(i,min,pos-1,trailing0);
        }
        return count;
    }

    private boolean isIncreasing(int n) {
        int d = n % 10;
        boolean increasing = true;
        while (increasing && n > 0) {
            int da = n % 10;
            n/=10;
            increasing = increasing && da <= d;
            d = da;
        }

        return increasing;
    }

    private boolean isDecreasing(int n) {
        int d = n % 10;
        boolean decreasing = true;
        while (decreasing && n > 0) {
            int da = n % 10;
            n/=10;
            decreasing = decreasing && da >= d;
            d = da;
        }

        return decreasing;
    }
}
